package lc2;
import java.util.*;
import org.junit.*;

public class Ex1838 {
    class Solution {
        public int maxFrequency(int[] nums, int k) {
            Arrays.sort(nums);
            int n = nums.length;
            int lo = 0, hi = 0;
            int res = 1;
    
            while (hi < n) {
                while (hi < n) {
                    if (hi > lo) {
                        int d = nums[hi] - nums[hi - 1];
                        int need = d * (hi - lo);
                        if (need > k) {
                            break;
                        } else {
                            k -= need;
                        }
                    }
                    hi++;
                }
    
                res = Math.max(res, hi - lo);
    
                if (hi == n) {
                    break;
                }
    
                //左指针右移
                k += nums[hi - 1] - nums[lo];
                lo++;
            }
    
            return res;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{3,9,6};
        System.out.println(s.maxFrequency(nums, 2));
    }
}
